package xyz.scootaloo.oj.leetcode

import cn.hutool.core.lang.Console
import org.junit.Test
import java.util.*

/**
 * @author flutterdash@qq.com
 * @since 2021/4/29 20:25
 */
class P334 {

    fun increasingTriplet(nums: IntArray): Boolean {
        if (nums.size < 3)
            return false

        val dp = IntArray(nums.size)
        dp[0] = 1
        for (i in 1 until nums.size) {
            val current = nums[i]
            var max = 0

            for (j in 0 until i) {
                if (nums[j] < current && dp[j] > max)
                    max = dp[j]
            }

            dp[i] = max + 1
            if (dp[i] >= 3)
                return true
        }

        return false
    }

    @Test
    fun test0() {
        val input0 = intArrayOf(20, 100, 10, 12, 5, 13)
        Console.log(increasingTriplet(input0))
    }

    @Test
    fun test1() {
        val input0 = intArrayOf(5, 1, 6)
        Console.log(increasingTriplet(input0))
    }

}
